package leetcode_2301_2400;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class LeeCode_2398 {
    public static void main(String[] args) {
        System.out.println(maximumRobots(new int[]{3, 6, 1, 3, 4}, new int[]{2, 1, 3, 4, 5}, 25));
        System.out.println(maximumRobots(new int[]{11,12,19}, new int[]{10,8,7}, 19));
    }
    private static int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int n = runningCosts.length;
        long[] sums = new long[n + 1];
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + runningCosts[i];
        }
        int l = 0, r = n;
        while (l < r){
            int m = (l + r + 1) >> 1;
            if (check(sums, chargeTimes, m, budget)){
                l = m;
            }else {
                r = m - 1;
            }
        }
        return l;
    }
    private static boolean check(long[] sums, int[] chargeTimes, int k, long budget){
        LinkedList<int[]> queue = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!queue.isEmpty() && queue.getLast()[0] <= chargeTimes[i]){
                queue.pollLast();
            }
            queue.add(new int[]{chargeTimes[i], i});
        }
        int l = 0, r = k - 1, n = chargeTimes.length;
        while (r < n){
            int max = queue.peek()[0];
            long cur = max + (sums[r + 1] - sums[l]) * k;
            if (cur <= budget){
                return true;
            }
            l++;
            r++;
            while (!queue.isEmpty() && queue.getFirst()[1] < l){
                queue.pollFirst();
            }
            if (r < n) {
                while (!queue.isEmpty() && queue.getLast()[0] <= chargeTimes[r]){
                    queue.pollLast();
                }
                queue.add(new int[]{chargeTimes[r], r});
            }
        }
        return false;
    }
    private static boolean check2(long[] sums, int[] chargeTimes, int k, long budget){
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] == o2[0]){
                return o1[1] - o2[1];
            }
            return o2[0] - o1[0];
        });
        for (int i = 0; i < k; i++) {
            queue.add(new int[]{chargeTimes[i], i});
        }
        int l = 0, r = k - 1, n = chargeTimes.length;
        while (r < n){
            while (queue.peek()[1] < l){
                queue.poll();
            }
            int max = queue.peek()[0];
            long cur = max + (sums[r + 1] - sums[l]) * k;
            if (cur <= budget){
                return true;
            }
            l++;
            r++;
            if (r < n)
                queue.add(new int[]{chargeTimes[r], r});
        }
        return false;
    }
}